In this letter we present an efficient root finding technique for a polynomial over GF(2m) when m is even number. The solutions that we have ever known are made to accelerate by our technique.
Minoru KURIBAYASHI Masakatu MORII
Quick Response (QR) code is a two dimensional barcode widely used in many applications. A standard QR code consists of black and white square modules, and it appears randomized patterns. By modifying the modules using certain rule, it is possible to display a logo image on the QR code. Such a QR code is called an aesthetic QR code. In this paper, we change the encoding method of the Reed-Solomon (RS) code to produce an aesthetic QR code without sacrificing its error correcting capability. The proposed method randomly produces candidates of RS blocks and finds the best one during encoding. Considering an image to be displayed, we also introduce a weighting function during random selection that classifies the visually important regions in the image. We further investigate the shape of modules which represents the image and consider the trade-off between the visual quality and its readability. As a result, we can produce a beautiful aesthetic QR code, which still can be decoded by standard QR code reader.
Toshihiro OHIGASHI Yoshiaki SHIRAISHI Masakatu MORII
In a key scheduling algorithm (KSA) of stream ciphers, a secret key is expanded into a large initial state. An internal state reconstruction method is known as a general attack against stream ciphers; it recovers the initial state from a given pair of plaintext and ciphertext more efficiently than exhaustive key search. If the method succeeds, then it is desirable that the inverse of KSA is infeasible in order to avoid the leakage of the secret key information. This paper shows that it is easy to compute a secret key from an initial state of RC4. We propose a method to recover an -bit secret key from only the first bits of the initial state of RC4 using linear equations with the time complexity less than that of one execution of KSA. It can recover the secret keys of which number is 2103.6 when the size of the secret key is 128 bits. That is, the 128-bit secret key can be recovered with a high probability when the first 128 bits of the initial state are determined using the internal state reconstruction method.
Makoto TAKITA Masanori HIROTOMO Masakatu MORII
Cassuto and Blaum presented a new coding framework for channels whose outputs are overlapping pairs of symbols in storage applications. Such channels are called symbol-pair read channels. Pair distance and pair error are used in symbol-pair read channels. Yaakobi et al. proved a lower bound on the minimum pair distance of cyclic codes. Furthermore, they provided a decoding algorithm for correcting pair errors using a decoder for cyclic codes, and showed the number of pair errors that can be corrected by their algorithm. However, their algorithm cannot correct all pair error vectors within half of the minimum pair distance. In this paper, we propose an efficient decoding algorithm for cyclic codes over symbol-pair read channels. It is based on the relationship between pair errors and syndromes. In addition, we show that the proposed algorithm can correct more pair errors than Yaakobi's algorithm.
Lee and Kwon proposed an anonymous authentication scheme based on Zhu et al.'s scheme. However, Lee et al.'s scheme has two disadvantages. Firstly, their scheme is vulnerable to off-line dictionary attacks. An adversary can guess a user password from the user's login messages eavesdropped by the adversary. Secondly, an authentication server called a home agent requires a verification table, which violates the original advantage of Zhu et al.'s scheme. That is, it increases the key management costs of the home agent. In this letter, we show the weaknesses of Lee et al.'s scheme and another three existing schemes. Then, we propose a new secure scheme without the verification table, while providing security for off-line dictionary attacks and other attacks except for a certain type of combined attacks.
Ken-ichi IWATA Masakatu MORII Tomohiko UYEMATSU
This paper describes an efficient and simple coding algorithm of universally optimal codes for stationary (ergodic) sources and noiseless channel with unequal symbol costs. The symbol cost indicates the required time (or space) for the transmission (or storage) of that symbol, and the cost of any code symbol depends only on that symbol. The proposed coding algorithm mainly consists of two parts. The first part is based on the well-known Ziv-Lempel coding algorighm proposed in 1978 (sometimes called LZ78), and the second part is based on the Varn coding algorithm. The coding algorithm asymptotically achieves an optimal average cost of codes for stationary sources, and also achieves an optimal cost of codes for stationary ergodic sources with probability one. Furthermore, the computational complexity of the proposed coding algorithm is linear with respect to the length of source sequence and coded sequence.
Minoru KURIBAYASHI Masakatu MORII
Digital fingerprinting is used to trace back illegal users, where unique ID known as digital fingerprints is embedded into a content before distribution. On the generation of such fingerprints, one of the important properties is collusion-resistance. Binary codes for fingerprinting with a code length of theoretically minimum order were proposed by Tardos, and the related works mainly focused on the reduction of the code length were presented. In this paper, we present a concrete and systematic construction of the Tardos's fingerprinting code using a chaotic map. Using a statistical model for correlation scores, the actual number of true-positive and false-positive detection is measured. The collusion-resistance of the generated fingerprinting codes is evaluated by a computer simulation.
Ryoichi TERAMURA Yasuo ASAKURA Toshihiro OHIGASHI Hidenori KUWAKADO Masakatu MORII
Conventional efficient key recovery attacks against Wired Equivalent Privacy (WEP) require specific initialization vectors or specific packets. Since it takes much time to collect the packets sufficiently, any active attack should be performed. An Intrusion Detection System (IDS), however, will be able to prevent the attack. Since the attack logs are stored at the servers, it is possible to prevent such an attack. This paper proposes an algorithm for recovering a 104-bit WEP key from any IP packets in a realistic environment. This attack needs about 36,500 packets with a success probability 0.5, and the complexity of our attack is equivalent to about 220 computations of the RC4 key setups. Since our attack is passive, it is difficult for both WEP users and administrators to detect our attack.
Sho SAKIKOYAMA Yosuke TODO Kazumaro AOKI Masakatu MORII
Linear cryptanalysis proposed by Matsui is one of the most effective attacks on block ciphers. Some attempts to improve linear cryptanalysis have been made since Matsui introduced. We focus on how to optimize linear cryptanalysis with such techniques, and we apply the optimized linear cryptanalysis on FEAL-8X. First, we evaluate two existing implementation methods so as to optimize the computation time of linear cryptanalysis. Method 1 removes redundant round function computations and optimizes the other computation of linear cryptanalysis by transforming it into bitwise operations. Method 2 transforms the computation of linear cryptanalysis into a matrix multiplication and reduces the time complexity of the multiplication using the fast Fourier transform (FFT). We implement both methods optimized for modern microprocessors and compare their computation time to clarify the appropriate method for practical cryptanalysis. From the result, we show that the superior implementation depends on the number of given known plaintexts (KPs) and that of guessed key bits. Furthermore, we show that these results enable us to select the superior method to implement linear cryptanalysis without another comparative experiment. By using the superior method, we implement the multiple linear cryptanalysis (MLC) on FEAL-8X. Our implementation can recover the secret key of FEAL-8X with 210KPs in practical computation time with non-negligible probability, and it is the best attack on FEAL-8X in data complexity.
Takuya OHARA Makoto TAKITA Masakatu MORII
Reduction of redundancy and improvement of error-correcting capability are essential research themes in the coding theory. The best known codes constructed in various ways are recorded in a database maintained by Markus Grassl. In this paper, we propose an algorithm to construct the best code using punctured codes and a supporting method for constructing the best codes. First, we define a new evaluation function to determine deletion bits and propose an algorithm for constructing punctured linear codes. 27 new best codes were constructed in the proposed algorithm, and 112 new best codes were constructed by further modifying those best codes. Secondly, we evaluate the possibility of increasing the minimum distance based on the relationship between code length, information length, and minimum distance. We narrowed down the target (n, k) code to try the best code search based on the evaluation and found 28 new best codes. We also propose a method to rapidly derive the minimum weight of the modified cyclic codes. A cyclic code loses its cyclic structure when it is modified, so we extend the k-sparse algorithm to use it for modified cyclic codes as well. The extended k-sparse algorithm is used to verify our newly constructed best code.
Hidenori KUWAKADO Masakatu MORII
Since Bellare and Ristenpart showed a multi-property preserving domain extension transform, the problem of the construction for multi-property hash functions has been reduced to that of the construction for multi-property compression functions. However, the Davies-Meyer compression function that is commonly used for standard hash functions is not a multi-property compression function. That is, in the ideal cipher model, the Davies-Meyer compression function is collision resistant, but it is not indifferentiable from a random oracle. In this paper, we show that the compression function proposed by Lai and Massey is a multi-property compression function. In addition, we show that the simplified version of the Lai-Massey compression function is also a multi-property compression function. The use of these compression functions enables us to construct multi-property hash functions by the multi-property preserving domain extension transform.
Yoshiaki SHIRAISHI Toshihiro OHIGASHI Masakatu MORII
Knudsen et al. proposed an efficient method based on a tree-search algorithm with recursive process for reconstructing the internal state of RC4 stream cipher. However, the method becomes infeasible for word size n > 5 because its time complexity to reconstruct the internal state is too large. This letter proposes a more efficient method than theirs. Our method can reconstruct the internal state by using the pre-known internal-state entries, which are fewer than their method.
In recent years, wireless LAN systems are widely used in campuses, offices, homes and so on. It is important to discuss the security aspect of wireless LAN networks in order to protect data confidentiality and integrity. The IEEE Standards Association formulated some security protocols, for example, Wired Equivalent Privacy (WEP) and Wi-Fi Protected Access Temporal Key Integrity Protocol (WPA-TKIP). However, these protocols have vulnerability for secure communication. In 2008, we proposed an efffective key recovery attack against WEP and it is called the TeAM-OK attack. In this paper, first, we present a different interpretation and the relation between other attacks and the TeAM-OK attack against WEP. Second, we present some existing attacks against WPA-TKIP and these attacks are not executable in a realistic environment. Then we propose an attack that is executable in a realistic environment against WPA-TKIP. This attack exploits the vulnerability implementation in the QoS packet processing feature of IEEE 802.11e. The receiver receives a falsification packet constructed as part of attack regardless of the setting of IEEE 802.11e. This vulnerability removes the attacker's condition that access points support IEEE 802.11e. We confirm that almost all wireless LAN implementations have this vulnerability. Therefore, almost all WPA-TKIP implementations cannot protect a system against the falsification attack in a realistic environment.
Ryusei NAGASAWA Keisuke FURUMOTO Makoto TAKITA Yoshiaki SHIRAISHI Takeshi TAKAHASHI Masami MOHRI Yasuhiro TAKANO Masakatu MORII
The Topics over Time (TOT) model allows users to be aware of changes in certain topics over time. The proposed method inputs the divided dataset of security blog posts based on a fixed period using an overlap period to the TOT. The results suggest the extraction of topics that include malware and attack campaign names that are appropriate for the multi-labeling of cyber threat intelligence reports.
Masanori HIROTOMO Masami MOHRI Masakatu MORII
Low-density parity-check (LDPC) codes are linear block codes defined by sparse parity-check matrices. The codes exhibit excellent performance under iterative decoding, and the weight distribution is used to analyze lower error probability of their decoding performance. In this paper, we propose a probabilistic method for computing the weight distribution of LDPC codes. The proposed method efficiently finds low-weight codewords in a given LDPC code by using Stern's algorithm, and stochastically computes the low part of the weight distribution from the frequency of the found codewords. It is based on a relation between the number of codewords with a given weight and the rate of generating the codewords in Stern's algorithm. In the numerical results for LDPC codes of length 504, 1008 and 4896, we could compute the weight distribution by the proposed method with greater accuracy than by conventional methods.
Makoto TAKITA Masanori HIROTOMO Masakatu MORII
In this paper, we discuss an algebraic decoding of BCH codes over symbol-pair read channels. The channels output overlapping pairs of symbols in storage applications. The pair distance and pair error are used in the channels. We define a polynomial that represents the positions of the pair errors as the error-locator polynomials and a polynomial that represents the positions of the pairs of a received pair vector in conflict as conflict-locator polynomial. In this paper, we propose algebraic methods for correcting two-pair and three-pair errors for BCH codes. First, we show the relation between the error-locator polynomials and the conflict-locator polynomial. Second, we show the relation among these polynomials and the syndromes. Finally, we provide how to correct the pair errors by solving equations including the relational expression by algebraic methods.
Ken-ichi IWATA Masakatu MORII Tomohiko UYEMATSU Eiji OKAMOTO
Many Ziv-Lempel algorithms have a similar property, that is, slow encoding and fast decoding. This paper proposes a simple improved Ziv-Lempel algorithm to encode a large amount of data quickly as well as compactly by using multiple-processor system.
Yuki FUNABIKI Yosuke TODO Takanori ISOBE Masakatu MORII
HIGHT is a 64-bit block lightweight cipher, which adopts the ARX-based generalized Feistel network, and it accepts a 128-bit key. It is a standard encryption algorithm in South Korea and also is internationally standardized by ISO/IEC 18033-3. Therefore, many third-party cryptanalyses have been proposed against HIGHT. Impossible differential and integral attacks are applied to reduced-round HIGHT, and especially, the impossible differential attack causes the 27-round attack, which is the current best attack under the single-key setting. In this paper, we propose some improved integral attacks against HIGHT. We first apply the division property to HIGHT and find new 19-round integral characteristics, which are improved by two rounds compared with the previous best ones. We append 9-round key recovery to these characteristics and it enables us to attack 28-round HIGHT. Its time complexity is 2127.02 where 263 chosen plaintexts and 2117 memory are required. Moreover, we can attack 29-round HIGHT if the full codebook is used, where its time and memory complexities are 2126.07 and 2118, respectively. It improves by two rounds compared with the previous best attack.
Hidenori KUWAKADO Masakatu MORII
The security notion of indifferentiability was proposed by Maurer, Renner, and Holenstein in 2004. In 2005, Coron, Dodis, Malinaud, and Puniya discussed the indifferentiability of hash functions. They have shown that the Merkle-Damgård construction is not secure in the sense of indifferentiability. In this paper, we analyze the security of single-block-length and rate-1 compression functions in the sense of indifferentiability. We formally show that all single-block-length and rate-1 compression functions, which include the Davies-Meyer compression function, are insecure. Furthermore, we show how to construct a secure single-block-length and rate-1 compression function in the sense of indifferentiability. This does not contradict our result above.
Yuhei WATANABE Takanori ISOBE Toshihiro OHIGASHI Masakatu MORII
RC4 is a well-known stream cipher designed by Rivest. Due to considerable cryptanalysis efforts over past 20 years, several kinds of statistic biases in a key stream of RC4 have been observed so far. Finally, practical full plaintext recovery attacks on RC4 in SSL/TLS were independently proposed by AlFardan et al. and Isobe et al. in 2013. Responded to these attacks, usage of RC4 has drastically decreased in SSL/TLS. However, according to the research by Trustworthy Internet Movement, RC4 is still used by some websites for the encryption on SSL/TLS. In this paper, we shows a new plaintext recovery attack for RC4 under the assumption of HTTPS. We develop a method for exploiting single-byte and double-byte biases together to efficiently guess the target bytes, while previous attacks use either single-byte biases or double-byte biases. As a result, target plaintext bytes can be extracted with higher probability than previous best attacks given 229 ciphertexts encrypted by randomly-chosen keys. In the most efficient case, the success probability of our attack are more than twice compared to previous best attacks.